// #include <iostream>
// #include <vector>
// #include <algorithm>
// #include <sstream>
// using namespace std;
//
// int main() {
//     vector<int> v;
//     int n;
//     cin>>n;
//     cin.ignore();
//     string s;
//     while (n--) {
//         getline(cin, s);
//         if (s.empty()) continue;
//         istringstream iss(s);
//         char cmd;
//         iss >> cmd;
//         if (cmd == '1') {
//             int x;
//             if (iss >> x) v.push_back(x);
//         } else if (cmd == '2') {
//             if (!v.empty()) v.pop_back();
//         } else if (cmd == '3') {
//             int i;
//             if (iss >> i && i >= 0 && i < v.size()) cout << v[i] << endl;
//         } else if (cmd == '4') {
//             int i, x;
//             if (iss >> i >> x && i >= 0 && i <= v.size()) v.insert(v.begin() + i + 1, x);
//         } else if (cmd == '5') {
//             sort(v.begin(), v.end());
//         } else if (cmd == '6') {
//             sort(v.begin(), v.end(), greater<int>());
//         } else if (cmd == '7') {
//             cout << v.size() << endl;
//         } else if (cmd == '8') {
//             for (size_t i = 0; i < v.size(); ++i) {
//                 if (i > 0) cout << " ";
//                 cout << v[i];
//             }
//             cout << endl;
//         }
//     }
//     return 0;
// }
//
// #include <iostream>
// #include <stack>
// using namespace std;
//
// int main() {
//     int n;
//     cin >> n;
//     stack<int> st;
//     while(n--){
//         string s;
//         cin>>s;
//         if(s=="push") {
//             int x;
//             cin>>x;
//             st.push(x);
//         } else if (s=="pop") {
//             if(!st.empty())
//                 st.pop();
//             else {
//                 cout<<"Empty"<<endl;
//             }
//         } else if (s=="query") {
//             if(!st.empty())
//                 cout<<st.top()<<endl;
//             else {
//                 cout<<"Empty"<<endl;
//             }
//         } else if (s=="size") {
//             cout<<st.size()<<endl;
//         }
//     }
//     return 0;
// }
// // 64 位输出请用 printf("%lld")
//
// #include <iostream>
// #include <queue>
// using namespace std;
//
// int main() {
//     int n;
//     cin >> n;
//     queue<int> q;
//
//     while (n--) {
//         int in;
//         cin >> in;
//         if (in == 1) {
//             int x;
//             cin >> x;
//             q.push(x);
//         } else if (in == 2) {
//             if (q.size()) {
//                 q.pop();
//             } else {
//                 cout << "ERR_CANNOT_POP" << endl;
//             }
//         } else if (in == 3) {
//             if (q.size()) {
//                 cout << q.front() << endl;
//             } else {
//                 cout << "ERR_CANNOT_QUERY" << endl;
//             }
//         } else if (in == 4) {
//             cout << q.size() << endl;
//         }
//     }
//     return 0;
// }
// // 64 位输出请用 printf("%lld")
//
// #include<bits/stdc++.h>
// #include <set>
// using namespace std;
//
// set<int> s;
//
// void insertValue(int x){
//     //TODO 实现插入逻辑
//     s.insert(x);
// }
// void eraseValue(int x){
//     //TODO 实现删除逻辑
//     s.erase(x);
// }
// int xInSet(int x){
//     //TODO 实现存在性检查
//     return s.count(x);
// }
// int sizeOfSet(){
//     //TODO 返回集合大小
//     return s.size();
// }
// int getPre(int x){
//     //TODO 实现找前驱
//     auto it = s.lower_bound(x);
//     if(it == s.begin()) return -1;
//     it--;
//     return *it;
// }
// int getBack(int x){
//     //TODO 实现找后继
//     auto it = s.upper_bound(x);
//     if(it == s.end()) return -1;
//     return *it;
// }
//
// int main(){
//     int q,op,x;
//     cin>>q;
//     while(q--){
//         cin>>op;
//         if(op==1){
//             cin>>x;
//             insertValue(x);
//         }
//         if(op==2){
//             cin>>x;
//             eraseValue(x);
//         }
//         if(op==3){
//             cin>>x;
//             if(xInSet(x)){
//                 cout<<"YES\n";
//             }else{
//                 cout<<"NO\n";
//             }
//         }
//         if(op==4){
//             cout<<sizeOfSet()<<endl;
//         }
//         if(op==5){
//             cin>>x;
//             cout<<getPre(x)<<endl;
//         }
//         if(op==6){
//             cin>>x;
//             cout<<getBack(x)<<endl;
//         }
//     }
//     return 0;
// }
//
// #include<bits/stdc++.h>
// using namespace std;
//
// multiset<int> ms;
//
// void insertValue(int x){
//     //TODO 实现插入逻辑
//     ms.insert(x);
// }
// void eraseValue(int x){
//     //TODO 实现删除逻辑
//     auto it = ms.find(x);
//     if (it != ms.end()) {
//         ms.erase(it);
//     }
// }
// int xCount(int x){
//     //TODO 求x在集合中的个数
//     return ms.count(x);
// }
// int sizeOfSet(){
//     //TODO 返回集合大小
//     return ms.size();
// }
// int getPre(int x){
//     //TODO 实现找前驱
//     auto it = ms.lower_bound(x);
//     if(it == ms.begin()) return -1;
//     it--;
//     return *it;
// }
// int getBack(int x){
//     //TODO 实现找后继
//     auto it = ms.upper_bound(x);
//     if(it == ms.end()) return -1;
//     return *it;
// }
//
// int main(){
//     int q,op,x;
//     cin>>q;
//     while(q--){
//         cin>>op;
//         if(op==1){
//             cin>>x;
//             insertValue(x);
//         }
//         if(op==2){
//             cin>>x;
//             eraseValue(x);
//         }
//         if(op==3){
//             cin>>x;
//             cout<<xCount(x)<<endl;
//         }
//         if(op==4){
//             cout<<sizeOfSet()<<endl;
//         }
//         if(op==5){
//             cin>>x;
//             cout<<getPre(x)<<endl;
//         }
//         if(op==6){
//             cin>>x;
//             cout<<getBack(x)<<endl;
//         }
//     }
//     return 0;
// }
//
// #include <functional>
// #include <iostream>
// #include <queue>
// #include <vector>
// using namespace std;
//
// priority_queue<int,vector<int>,greater<int>> pq;
//
// int main() {
//     int n;
//     cin>>n;
//     while (n--) {
//         int in;
//         cin>>in;
//         if(in==1){
//             int x;
//             cin>>x;
//             pq.push(x);
//         } else if (in==2) {
//             cout<<pq.top()<<endl;
//         } else if (in==3) {
//             pq.pop();
//         }
//     }
//     return 0;
// }
// // 64 位输出请用 printf("%lld")
//
// #include <iostream>
// #include <unordered_map>
// using namespace std;
//
// int main() {
//     int n;
//     cin >> n;
//
//     unordered_map<unsigned long long, unsigned long long> f_map;
//     unsigned long long total_sum = 0;
//
//     for (unsigned long long i = 1; i <= n; ++i) {
//         unsigned long long x, y;
//         cin >> x >> y;
//
//         unsigned long long ans_i = 0;
//         if (f_map.count(x)) {
//             ans_i = f_map[x];
//         }
//
//         total_sum += i * ans_i;
//
//         f_map[x] = y;
//     }
//
//     cout << total_sum << endl;
//
//     return 0;
// }
// // 64 位输出请用 printf("%lld")
//
// #include <iostream>
// #include <vector>
// using namespace std;
//
// int main() {
//     vector<int> v1(3);
//     int num = 0;
//     for(int i = 0;i<3;i++){
//         cin>>v1[i];
//     }
//     int a1,a2,a3;
//     cin>>a1>>a2>>a3;
//     vector<vector<int>> v2 ={{a1,a2,a3},{a1,a3,a2},{a2,a1,a3},{a2,a3,a1},{a3,a1,a2},{a3,a2,a1}};
//     for(int i = 0;i<6;i++){
//         num = 0;
//         for(int j=0;j<3;j++){
//             if(v2[i][j] > v1[j]){
//                 num++;
//                 if(num>=2){
//                     cout<<"Yes"<<endl;
//                     return 0;
//                 }
//             }
//         }
//     }
//     cout<<"No"<<endl;
//     return 0;
// }
// // 64 位输出请用 printf("%lld")
//
// #include <climits>
// #include <iostream>
// using namespace std;
//
// int main() {
//     string s,t;
//     cin >>s>>t;
//     int len_s = s.size();
//     int len_t = t.size();
//     if (len_s > len_t) return -1;
//
//     int min_cost = INT_MAX;
//     for (int i = 0; i <= len_t - len_s; ++i) {
//         string sub = t.substr(i, len_s);
//         int cost = 0;
//         for (int j = 0; j < len_s; ++j) {
//             char c1 = s[j];
//             char c2 = sub[j];
//             int diff = abs(c1 - c2);
//             cost += min(diff, 26 - diff);
//         }
//         min_cost = min(min_cost, cost);
//     }
//     cout<<min_cost;
//     return 0;
// }
// // 64 位输出请用 printf("%lld")

// /**
//  * struct ListNode {
//  *	int val;
//  *	struct ListNode *next;
//  *	ListNode(int x) : val(x), next(nullptr) {}
//  * };
//  */
// class Solution {
// public:
//     /**
//      * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//      *
//      *
//      * @param head ListNode类
//      * @return ListNode类
//      */
//     ListNode* ReverseList(ListNode* head) {
//         ListNode* prev=nullptr,*next=nullptr,*cur=head;
//         while(cur!=nullptr) {
//             next = cur->next;
//             cur->next=prev;
//             prev =cur;
//             cur = next;
//         }
//         return prev;
//     }
// };

//
// class Solution {
// public:
//     ListNode* reverseBetween(ListNode* head, int m, int n) {
//         if (!head || !head->next || m == n) return head;
//
//         ListNode dummy(0);
//         dummy.next = head;
//         ListNode* pre = &dummy;
//
//         // 移动到反转起始点的前一个节点
//         for (int i = 1; i < m; ++i) {
//             pre = pre->next;
//         }
//
//         ListNode* cur = pre->next;
//         ListNode* next = nullptr;
//
//         // 反转m到n之间的节点
//         for (int i = m; i < n; ++i) {
//             next = cur->next;
//             cur->next = next->next;
//             next->next = pre->next;
//             pre->next = next;
//         }
//
//         return dummy.next;
//     }
// // };
//
// /**
//  * struct ListNode {
//  *	int val;
//  *	struct ListNode *next;
//  *	ListNode(int x) : val(x), next(nullptr) {}
//  * };
//  */
// class Solution {
// public:
//     /**
//      * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//      *
//      *
//      * @param head ListNode类
//      * @param k int整型
//      * @return ListNode类
//      */
//     ListNode* reverseKGroup(ListNode* head, int k) {
//         ListNode dummy(0);
//         ListNode *cur = head;
//         dummy.next = head;
//         ListNode* prev=&dummy;
//         ListNode* next = nullptr;
//
//         int sz = 0,pos = 0;
//         while (cur != nullptr) {
//             cur =cur ->next;
//             sz++;
//         }
//         cur = head;
//         for (pos =0; pos + k <= sz; pos+=k) {
//
//             ListNode* groupPrev = prev;
//             ListNode* groupHead = cur;
//             for (int i = 0; i < k; ++i) {
//                 next = cur->next;
//                 cur->next=prev;
//                 prev =cur;
//                 cur = next;
//             }
//
//             groupPrev->next = prev;
//             groupHead->next = cur;
//
//             prev = groupHead;
//         }
//         return dummy.next;
//     }
// };
//
// /**
//  * struct ListNode {
//  *	int val;
//  *	struct ListNode *next;
//  *	ListNode(int x) : val(x), next(nullptr) {}
//  * };
//  */
// class Solution {
// public:
//     /**
//      * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//      *
//      *
//      * @param pHead1 ListNode类
//      * @param pHead2 ListNode类
//      * @return ListNode类
//      */
//     ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
//         ListNode dummy(0);
//         ListNode *cur = &dummy;
//         ListNode *cur1 = pHead1,*cur2 = pHead2;
//         while (cur1 && cur2) {
//             if (cur1->val < cur2 ->val) {
//                 ListNode *Node = new ListNode(cur1->val);
//                 cur ->next =Node;
//                 cur1 = cur1->next;
//                 cur =cur->next;
//             } else {
//                 ListNode *Node = new ListNode(cur2->val);
//                 cur ->next =Node;
//                 cur2 = cur2->next;
//                 cur =cur->next;
//             }
//         }
//         while (cur1) {
//             ListNode *Node = new ListNode(cur1->val);
//             cur->next =Node;
//             cur =cur->next;
//             cur1=cur1->next;
//         }
//         while (cur2) {
//             ListNode *Node = new ListNode(cur2->val);
//             cur->next =Node;
//             cur =cur->next;
//             cur2=cur2->next;
//         }
//         return dummy.next;
//     }
// };
//
// #include <queue>
// #include <vector>
// class Solution {
// public:
//     /**
//      * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//      *
//      *
//      * @param lists ListNode类vector
//      * @return ListNode类
//      */
//     ListNode* mergeKLists(vector<ListNode*>& lists) {
//         std::priority_queue<int,vector<int>,greater<int>> pq;
//         for (auto e:lists) {
//             while (e) {
//                 pq.push(e->val);
//                 e = e->next;
//             }
//         }
//
//         ListNode dummp(0);
//         ListNode *head=&dummp;
//         while (pq.size()) {
//             ListNode *Node = new ListNode(pq.top());
//             head->next=Node;
//             head=head->next;
//             pq.pop();
//         }
//         return dummp.next;
//     }
// };
//
// class Solution {
// public:
//     bool hasCycle(ListNode *head) {
//         if (!head) {
//             return false;
//         }
//         ListNode *slow = head;
//         ListNode *fast = head;
//         while (fast != nullptr && fast->next != nullptr) {
//             slow = slow -> next;
//             fast = fast -> next -> next;
//             if(slow==fast) {
//                 return true;
//             }
//         }
//         return false;
//     }
// };
//
//
// /*
// struct ListNode {
//     int val;
//     struct ListNode *next;
//     ListNode(int x) :
//         val(x), next(NULL) {
//     }
// };
// */
// class Solution {
// public:
//     ListNode* EntryNodeOfLoop(ListNode* pHead) {
//         if (!pHead || !pHead->next) {
//             return nullptr;
//         }
//         ListNode *slow = pHead;
//         ListNode *fast = pHead;
//         while(fast!=nullptr && fast->next!=nullptr) {
//             slow = slow ->next;
//             fast = fast->next->next;
//             if(slow == fast) {
//                 slow = pHead;
//                 break;
//             }
//         }
//         if(slow!=pHead) {
//             return nullptr;
//         }
//         while(slow!=fast) {
//             slow=slow->next;
//             fast=fast->next;
//         }
//         return slow;
//     }
// };
//
// class Solution {
// public:
//     /**
//      * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//      *
//      *
//      * @param nums int整型vector
//      * @param target int整型
//      * @return int整型
//      */
//     int search(vector<int>& nums, int target) {
//         int left = 0;
//         int right = nums.size()-1;
//         while (left<=right) {
//             int middle = left + (right-left)/2;
//             if(nums[middle] > target) {
//                 right = middle-1;
//             } else if (nums[middle] < target){
//                 left = middle+1;
//             } else {
//                 return middle;
//             }
//         }
//         return -1;
//     }
// };
// /**
//  * struct TreeNode {
//  *	int val;
//  *	struct TreeNode *left;
//  *	struct TreeNode *right;
//  *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
//  * };
//  */
// class Solution {
// public:
//     /**
//      * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//      *
//      *
//      * @param root TreeNode类
//      * @return int整型vector<vector<>>
//      */
//     vector<vector<int> > levelOrder(TreeNode* root) {
//         vector<vector<int>> res;
//         if(root==nullptr) return res;
//         queue<TreeNode*> q;
//         q.push(root);
//         while (q.size()) {
//             vector<int> level;
//             int n = q.size();
//             for (int i =0;i<n;i++) {
//                 TreeNode *tmp = q.front();
//                 level.push_back(tmp->val);
//                 q.pop();
//                 if (tmp->left) {
//                     // q.push(tmp->left);
//                 // }
//                 if (tmp->right) {
//                     q.push(tmp->right);
//                 }
//             }
//             res.push_back(level);
//         }
//         return res;
//     }
// };
//
// /**
//  * struct TreeNode {
//  *	int val;
//  *	struct TreeNode *left;
//  *	struct TreeNode *right;
//  *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
//  * };
//  */
// #include <algorithm>
// #include <queue>
// #include <vector>
// class Solution {
// public:
//     /**
//      * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//      *
//      *
//      * @param pRoot TreeNode类
//      * @return int整型vector<vector<>>
//      */
//     vector<vector<int> > Print(TreeNode* pRoot) {
//         queue<TreeNode*> q;
//         vector<vector<int>> res;
//         if(pRoot == nullptr) return res;
//         q.push(pRoot);
//         int num = 1;
//         while(q.size()) {
//             vector<int> v;
//             int len = q.size();
//             for(int i =0;i<len;i++) {
//                 TreeNode* tmp = q.front();
//                 v.push_back(tmp->val);
//
//                 if(tmp->left) {
//                     q.push(tmp->left);
//                 }
//                 if(tmp->right) {
//                     q.push(tmp->right);
//                 }
//
//                 q.pop();
//             }
//             if(num%2==0) {
//                 reverse(v.begin(), v.end());
//             }
//             res.push_back(v);
//             num++;
//         }
//         return res;
//     }
// };

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型
     */
    int maxDepth(TreeNode* root) {
        if(root==nullptr) return 0;
        return max(maxDepth(root->left),maxDepth(root->right))+1;
    }
};